package dongtaiguihua;

public class CoinsV1 {
    //1 定义一个状态，方法,凑够n分的最少硬币个数
//dp(n):凑够n分的最少硬币个数
    static int coinChange(int n){
//递归基
        if(n <1){ return Integer.MAX_VALUE;}
//2 确定初始状态
        if(n==1||n==5||n==20|n==25){ return 1;}
//3、确定状态的转移方程：dp(n)与dp(n-1)的关系，
/**
 * 如果第一次选择了1分；coinChange(n)=coinChange(n-1)+1
 * 如果第一次选择了5分；coinChange(n)=coinChange(n-5)+1
 * 如果第一次选择了20分；coinChange(n)=coinChange(n-20)+1
 * 如果第一次选择了25分；coinChange(n)=coinChange(n-25)+1
 * 以上四种情况选择哪一种呢？应该选择的是硬币个数最少的这种
 */
        final int min1 = Math.min(coinChange(n - 1), coinChange(n - 5));
        final int min2 = Math.min(coinChange(n - 20), coinChange(n - 25));
        return Math.min(min1, min2) + 1;
    }
    public static void main(String[] args) {
        System.out.println(coinChange(841));
    }
}
